home *** CD-ROM | disk | FTP | other *** search
/ ADA Programming Guide / ADA Programming Guide.iso / ada_gnu / adainc / s-tasque.adb < prev    next >
Text File  |  1996-01-30  |  9KB  |  305 lines

  1. ------------------------------------------------------------------------------
  2. --                                                                          --
  3. --                 GNU ADA RUNTIME LIBRARY (GNARL) COMPONENTS               --
  4. --                                                                          --
  5. --                 S Y S T E M . T A S K I N G . Q U E U I N G              --
  6. --                                                                          --
  7. --                                  B o d y                                 --
  8. --                                                                          --
  9. --                             $Revision: 1.7 $                             --
  10. --                                                                          --
  11. --       Copyright (c) 1991,1992,1993,1994, FSU, All Rights Reserved        --
  12. --                                                                          --
  13. -- GNARL is free software; you can redistribute it  and/or modify it  under --
  14. -- terms  of  the  GNU  Library General Public License  as published by the --
  15. -- Free Software  Foundation;  either version 2, or (at  your  option)  any --
  16. -- later  version.  GNARL is distributed  in the hope that  it will be use- --
  17. -- ful, but but WITHOUT ANY WARRANTY;  without even the implied warranty of --
  18. -- MERCHANTABILITY  or  FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Gen- --
  19. -- eral Library Public License  for more details.  You should have received --
  20. -- a  copy of the GNU Library General Public License along with GNARL;  see --
  21. -- file COPYING.LIB.  If not,  write to the  Free Software Foundation,  675 --
  22. -- Mass Ave, Cambridge, MA 02139, USA.                                      --
  23. --                                                                          --
  24. ------------------------------------------------------------------------------
  25.  
  26. with System.Task_Primitives; use System.Task_Primitives;
  27.  
  28. package body System.Tasking.Queuing is
  29.  
  30.    --  Entry Queues implemented as doubly linked list, priority ordered
  31.  
  32.    -------------
  33.    -- Enqueue --
  34.    -------------
  35.  
  36.    --  Enqueue call priority ordered, FIFO at same priority level
  37.  
  38.    procedure Enqueue (E : in out Entry_Queue; Call : Entry_Call_Link) is
  39.       Temp : Entry_Call_Link := E.Head;
  40.    begin
  41.       if Temp = null then
  42.          Call.Prev := Call;
  43.          Call.Next := Call;
  44.          E.Head := Call;
  45.          E.Tail := Call;
  46.       else
  47.          loop  --  find the entry that the new guy should precede
  48.             exit when Call.Prio > Temp.Prio;
  49.             Temp := Temp.Next;
  50.             if Temp = E.Head then
  51.                Temp := null;
  52.                exit;
  53.             end if;
  54.          end loop;
  55.  
  56.          if Temp = null then -- insert at tail
  57.             Call.Prev := E.Tail;
  58.             Call.Next := E.Head;
  59.             E.Tail := Call;
  60.          else
  61.             Call.Prev := Temp.Prev;
  62.             Call.Next := Temp;
  63.  
  64.             if Temp = E.Head then -- insert at head
  65.                E.Head := Call;
  66.             end if;
  67.          end if;
  68.  
  69.          Call.Prev.Next := Call;
  70.          Call.Next.Prev := Call;
  71.  
  72.       end if;
  73.    end Enqueue;
  74.  
  75.    -------------
  76.    -- Dequeue --
  77.    -------------
  78.  
  79.    --  Dequeue call from entry_queue E
  80.  
  81.    procedure Dequeue (E : in out Entry_Queue; Call : Entry_Call_Link) is
  82.       Prev : Entry_Call_Link;
  83.  
  84.    begin
  85.       --  If empty queue, simply return
  86.  
  87.       if E.Head = null then
  88.          return;
  89.       end if;
  90.  
  91.       Call.Prev.Next := Call.Next;
  92.       Call.Next.Prev := Call.Prev;
  93.  
  94.       if E.Head = Call then
  95.          if E.Tail = Call then
  96.             E.Head := null; --  case of one element
  97.             E.Tail := null;
  98.          else
  99.             E.Head := Call.Next;
  100.          end if;
  101.       elsif E.Tail = Call then
  102.          E.Tail := Call.Prev;
  103.       end if;
  104.  
  105.       --  Successfully dequeued
  106.  
  107.       Call.Prev := null;
  108.       Call.Next := null;
  109.  
  110.    end Dequeue;
  111.  
  112.    ----------
  113.    -- Head --
  114.    ----------
  115.  
  116.    --  Return the head of entry_queue E
  117.  
  118.    function Head (E : in Entry_Queue) return Entry_Call_Link is
  119.    begin
  120.       return E.Head;
  121.    end Head;
  122.  
  123.    ------------------
  124.    -- Dequeue_Head --
  125.    ------------------
  126.  
  127.    --  Remove and return the head of entry_queue E
  128.  
  129.    procedure Dequeue_Head
  130.      (E    : in out Entry_Queue;
  131.       Call : out Entry_Call_Link)
  132.    is
  133.       Temp : Entry_Call_Link;
  134.  
  135.    begin
  136.       --  If empty queue, return null pointer
  137.  
  138.       if E.Head = null then
  139.          Call := null;
  140.          return;
  141.       end if;
  142.  
  143.       Temp := E.Head;
  144.  
  145.       if E.Head = E.Tail then
  146.          E.Head := null; --  case of one element
  147.          E.Tail := null;
  148.       else
  149.          E.Head := Temp.Next;
  150.          Temp.Prev.Next := Temp.Next;
  151.          Temp.Next.Prev := Temp.Prev;
  152.       end if;
  153.  
  154.       --  Successfully dequeued
  155.  
  156.       Temp.Prev := null;
  157.       Temp.Next := null;
  158.       Call := Temp;
  159.    end Dequeue_Head;
  160.  
  161.    -------------
  162.    -- Onqueue --
  163.    -------------
  164.  
  165.    --  Return True if Call is on any entry_queue at all
  166.  
  167.    function Onqueue (Call : Entry_Call_Link) return Boolean is
  168.    begin
  169.       --  Utilize the fact that every queue is circular, so if Call
  170.       --  is on any queue at all, Call.Next must NOT be null.
  171.  
  172.       return Call.Next /= null;
  173.    end Onqueue;
  174.  
  175.    -------------------
  176.    -- Count_Waiting --
  177.    -------------------
  178.  
  179.    --  Return number of calls on the waiting queue of E
  180.  
  181.    function Count_Waiting (E : in Entry_Queue) return Natural is
  182.       Count : Natural;
  183.       Temp : Entry_Call_Link;
  184.  
  185.    begin
  186.       Count := 0;
  187.  
  188.       if E.Head /= null then
  189.          Temp := E.Head;
  190.  
  191.          loop
  192.             Count := Count + 1;
  193.             exit when E.Tail = Temp;
  194.             Temp := Temp.Next;
  195.          end loop;
  196.       end if;
  197.  
  198.       return Count;
  199.    end Count_Waiting;
  200.  
  201.    ----------------------------
  202.    -- Select_Task_Entry_Call --
  203.    ----------------------------
  204.  
  205.    --  Select an entry for rendezvous
  206.  
  207.    procedure Select_Task_Entry_Call
  208.      (Acceptor     : Utilities.ATCB_Ptr;
  209.       Open_Accepts : Accept_List_Access;
  210.       Call         : out Entry_Call_Link;
  211.       Selection    : out Select_Index)
  212.    is
  213.       Entry_Call  : Entry_Call_Link;
  214.       Temp_Call   : Entry_Call_Link;
  215.       Entry_Index : Task_Entry_Index;
  216.       Temp_Entry  : Task_Entry_Index;
  217.       TAS_Result  : Boolean;
  218.    begin
  219.       loop
  220.          Entry_Call := null;
  221.  
  222.          for J in Open_Accepts'Range loop
  223.             Temp_Entry := Open_Accepts (J).S;
  224.             if Temp_Entry /= Null_Task_Entry then
  225.                Temp_Call := Head (Acceptor.Entry_Queues (Temp_Entry));
  226.                if Temp_Call /= null and then
  227.                  (Entry_Call = null or else
  228.                   Entry_Call.Prio < Temp_Call.Prio)
  229.                then
  230.                   Entry_Call := Head (Acceptor.Entry_Queues (Temp_Entry));
  231.                   Entry_Index := Temp_Entry;
  232.                   Selection := J;
  233.                end if;
  234.             end if;
  235.          end loop;
  236.  
  237.          if Entry_Call = null then
  238.             Selection := No_Rendezvous;
  239.             exit;
  240.          end if;
  241.  
  242.          --  Guard is open
  243.          Dequeue_Head (Acceptor.Entry_Queues (Entry_Index), Entry_Call);
  244.          Test_And_Set (Entry_Call.Call_Claimed'Address, TAS_Result);
  245.          exit when TAS_Result;
  246.          --  TAS_Result = False only when the call is already canceled
  247.          --  in that case, we go on to the next call on the queue
  248.       end loop;
  249.  
  250.       Call := Entry_Call;
  251.  
  252.    end Select_Task_Entry_Call;
  253.  
  254.    ---------------------------------
  255.    -- Select_Protected_Entry_Call --
  256.    ---------------------------------
  257.  
  258.    --  Select an entry of a protected object
  259.  
  260.    procedure Select_Protected_Entry_Call
  261.      (Object    : Protection_Access;
  262.       Barriers  : Barrier_Vector;
  263.       Call      : out Entry_Call_Link)
  264.    is
  265.       Entry_Call  : Entry_Call_Link;
  266.       Temp_Call   : Entry_Call_Link;
  267.       Entry_Index : Protected_Entry_Index;
  268.       TAS_Result  : Boolean;
  269.    begin
  270.       loop
  271.          Entry_Call := null;
  272.  
  273.          for J in Barriers'Range loop
  274.             if Barriers (J) then
  275.                Temp_Call := Head (Object.Entry_Queues (J));
  276.                if Temp_Call /= null and then
  277.                   (Entry_Call = null or else
  278.                    Entry_Call.Prio < Temp_Call.Prio)
  279.                then
  280.                   Entry_Call := Temp_Call;
  281.                   Entry_Index := J;
  282.                end if;
  283.             end if;
  284.          end loop;
  285.  
  286.          exit when Entry_Call = null;
  287.  
  288.          --  Barrier is open
  289.          Dequeue_Head (Object.Entry_Queues (Entry_Index), Entry_Call);
  290.          if Entry_Call.Abortable then
  291.             Test_And_Set (Entry_Call.Call_Claimed'Address, TAS_Result);
  292.             exit when TAS_Result;
  293.          --  If call is not abortable, it has already been claimed for us
  294.          else
  295.             exit;
  296.          end if;
  297.  
  298.       end loop;
  299.  
  300.       Call := Entry_Call;
  301.  
  302.    end Select_Protected_Entry_Call;
  303.  
  304. end System.Tasking.Queuing;
  305.